#include <iostream>
#include <list>
#include <set>
#include <map>

using namespace std;

namespace Disjoint
{
	struct Set 
	{
		size_t _id = 0;
		size_t _rank = 0;

		Set* _pParent = this;
	};

	struct Forest
	{
		std::map<size_t, Set*> _map;

		Set* make(size_t id);
		Set* find(size_t id);
		Set* find(Set* x);
		Set* link(size_t x, size_t y);
		void show(std::ostream& os) const;
	};
}

int main()
{
	Disjoint::Forest f;
	f.make(1);
	f.make(2);
	f.make(3);
	f.make(4);
	f.make(5);
	f.make(6);
	f.make(7);
	f.make(8);
	f.make(9);
	f.make(10);
	f.link(2, 4);
	f.link(5, 7);
	f.link(1, 3);
	f.link(8, 9);
	f.link(1, 2);
	f.link(5, 6);
	f.link(2, 3);
	f.show(cout);

	return 0;
}

namespace Disjoint
{
	Set* Forest::make(size_t id)
	{
		if (!id)
			return NULL;

		Set* pSet = new Set;
		pSet->_id = id;
		_map[id] = pSet;
		return pSet;
	}

	Set* Forest::find(size_t id)
	{
		auto it = _map.find(id);
		if (it == _map.end())
			return NULL;

		return find(it->second);
	}

	Set* Forest::find(Set* x)
	{
		if (!x)
			return NULL;

		if (x != x->_pParent)
			x->_pParent = find(x->_pParent);

		return x->_pParent;
	}

	Set* Forest::link(size_t x, size_t y)
	{
		auto pX = find(x);
		if (!pX)
			return NULL;

		auto pY = find(y);
		if (!pY)
			return NULL;

		if (pX == pY)
			return pX;

		if (pX->_rank > pY->_rank)
		{
			pY->_pParent = pX;
			return pX;
		}

		pX->_pParent = pY;
		if (pX->_rank == pY->_rank)
			++pY->_rank;

		return pY;
	}

	void Forest::show(std::ostream& os) const
	{
		struct OsSet
		{
			size_t _id = 0;
			std::map<size_t, OsSet> _cld;

			void show(std::ostream& os) const
			{
				if (_id)
					os << _id;

				if (_cld.empty())
					return;

				if (_id)
					os << "=";

				os << "{";
				bool first = true;
				for (std::map<size_t, OsSet>::const_iterator it = _cld.begin(); it != _cld.end(); ++it)
				{
					if (first) first = false;
					else os << ",";

					it->second.show(os);
				}
				os << "}";
			}
		} osSet;

		std::set<size_t> finish;
		for (auto [id, pData] : _map)
		{
			if (finish.find(id) != finish.end())
				continue;

			const Set* pSet = pData;
			std::list<size_t> ids;
			while (true)
			{
				ids.push_front(pSet->_id);
				
				if (pSet == pSet->_pParent)
					break;
				else
					pSet = pSet->_pParent;
			}

			std::map<size_t, OsSet>* pCld = &osSet._cld;
			for (auto i : ids)
			{
				std::map<size_t, OsSet>::iterator it = pCld->find(i);
				if (it != pCld->end())
				{
					pCld = &it->second._cld;
					continue;
				}

				OsSet& tmp = (*pCld)[i];
				tmp._id = i;
				pCld = &tmp._cld;
				finish.insert(i);
			}
		}

		osSet.show(os);
	}
}